#include <iostream>
#include <stdlib.h>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x)
	:val(x), 
	left(nullptr), 
	right(nullptr)
	{}
};


//非递归实现后序遍历
void PostOrder(TreeNode* root)
{
	if (root == nullptr) return;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	TreeNode* prev = nullptr;//注意他定义的位置
	while (!st.empty() || cur)
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->left;
		}

		TreeNode* top = st.top();
		
		
		/*if (top->right && top->right != prev)
		{
			cur = top->right;
		}
		else if (top->right == nullptr || prev == top->right)
		{
			cout << top->val << endl;
			st.pop();
			prev = top;
		}*/

		//或者
		if (top->right == nullptr || top->right == prev)
		{
			cout << top->val << endl;
			prev = st.top();
			st.pop();

		}
		else
		{
			cur = top->right;
		}
	}
}

//递归实现后序遍历
void PostOrder1(TreeNode* root)
{
	if (!root) return;
	PostOrder1(root->left);
	PostOrder1(root->right);
	cout << root->val << endl;

}


//递归实现前序
void PerOrder(TreeNode* root)
{
	if (!root) return;
	cout << root->val << endl;
	PerOrder(root->left);
	PerOrder(root->right);

}

//非递归实现前序
void PreOrder1(TreeNode* root)
{
	stack<TreeNode*> st;
	TreeNode* cur = root;
	while (cur || !st.empty())
	{
		while (cur)
		{
			cout << cur->val << endl;
			st.push(cur);
			cur = cur->left;
		}

		TreeNode* top = st.top();
		st.pop();
		cur = top->right;
		
	}

}

//非递归中序
void InOrder(TreeNode* root)
{
	stack<TreeNode*> st;
	TreeNode* cur = root;
	
	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->left;
		}

		TreeNode* top = st.top();
		st.pop();
		cout << top->val << endl;
		cur = top->right;
	}
}


int main()
{
	//      1
   //     /   \
   //    2     3
  //   /  \       
//    4    5 
	TreeNode* root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(3);
	root->left->left = new TreeNode(4);
	root->left->right = new TreeNode(5);
	

	PostOrder(root);
	//PreOrder1(root);

	//InOrder(root);

	
	
	return 0;
}